package interview.huawei.training.p43;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[][] d = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNextInt()) {
            int m = scanner.nextInt();
            int n = scanner.nextInt();
            int[][] maze = new int[m][n];
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    maze[i][j] = scanner.nextInt();
                }
            }
            boolean[][] visited = new boolean[m][n];
            int[][][] prevs = new int[m][n][2];

            // 使用广度优先遍历求解最短路径
            // 定义一个队列
            Deque<Integer[]>  queue = new ArrayDeque<>();
            // 将起点入队
            queue.addLast(new Integer[] {0, 0});
            visited[0][0] = true;
            prevs[0][0][0] = 0;
            prevs[0][0][1] = 0;
            a:while(!queue.isEmpty()) {
                // 出队
                Integer[] pos = queue.removeFirst();
                for(int i = 0; i < d.length; i++) {
                    int x = pos[0] + d[i][0];
                    int y = pos[1] + d[i][1];
                    if(inArea(x, y, m, n) && !visited[x][y] && maze[x][y] != 1) {
                        queue.addLast(new Integer[] {x, y});
                        visited[x][y] = true;
                        prevs[x][y][0] = pos[0];
                        prevs[x][y][1] = pos[1];
                        if(x == m - 1 && y == n - 1) {
                            break a;
                        }
                    }
                }
            }

            // 遍历路径
            ArrayList<Integer[]> path = new ArrayList<>();
            int curX = m - 1, curY = n - 1;
            int tempX;
            while(curX > 0 || curY > 0) {
                path.add(new Integer[] {curX, curY});
                tempX = prevs[curX][curY][0];
                // 在curY取出来之前，curX的值暂时不能变
                curY = prevs[curX][curY][1];
                curX = tempX;
            }
            path.add(new Integer[]{curX, curY});
            Collections.reverse(path);
            for(Integer[] pos : path) {
                System.out.println("(" + pos[0] + "," + pos[1] + ")");
            }
        }
    }
    
    private static boolean inArea(int x, int y, int m, int n) {
        return x >=0 && x < m && y >= 0 && y < n;
    }
}